package leetcode.editor.cn.q1_300.q50;

/**
 * ok，这是第一道自己分析出来的动态规划题：
 * <p>
 * 对于 n 来说，左子树为 i 个节点，右子树为 n-i-1 个节点
 * 也就是说 dp[n] = dp[1]*dp[n-2] + dp[2]*dp[n-2] + ... + dp[i]*dp[n-i-1]
 *
 * of course，可以用打表法推公式出来。。。但是这个题没推出来，具体公式可以看官方答案
 *
 * @author qidi
 * @date 2021-12-28 13:28:52
 */
class Q0096_UniqueBinarySearchTrees {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int numTrees(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;

            for (int size = 2; size <= n; size++) {
                for (int i = 0; i < size; i++) {
                    dp[size] += dp[i] * dp[size - i - 1];
                }
            }

            return dp[n];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0096_UniqueBinarySearchTrees().new Solution();
        System.out.println(solution.numTrees(4));
        System.out.println(solution.numTrees(10));
    }
}